# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
# class Solution:
#     def swapPairs(self, head):
#         if not head or head.next==None:
#             return head
#         i=head
#         head = i.next
#         if i and i.next!=None:
#             j = i.next
#             i.next = j.next
#             j.next = i
#             pre = i
#             i = i.next
#
#         while i and i.next!=None:
#
#             j = i.next
#             i.next = j.next
#             j.next = i
#             pre.next = j
#             pre = i
#             i = i.next
#
#         return head


#递归解决
class Solution:
    def swapPairs(self, head):
        if not head or head.next == None:
            return
        newhead = head.next
        newhead.next = head
        head.next = self.swapPairs(newhead)
        return newhead



if __name__ == '__main__':
    one = ListNode(1)
    two = ListNode(2)
    tree = ListNode(3)
    four = ListNode(4)
    one.next = two
    two.next = tree
    tree.next = four
    four.next = None
    S = Solution()
    head = S.swapPairs(one)
    print(head.next.next.next.val)

